/**
 *  @file FindSubsequence.c
 *  @desc 判断链表 lb 是否为链表 la 的子序列（非连续匹配）
 *        使用简单的双层遍历算法，未使用KMP等高效算法
 *  @author WangBlue (wangjiping596@gmail.com)
 *  @date 2025-07-18 14:28
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// ------------------------- 链表结构定义 -------------------------

/**
 * @brief 单链表结点结构（带头结点）
 */
typedef struct node {
    char data;              ///< 数据域，存储字符
    struct node *next;      ///< 指针域，指向下一个节点
} node, *link;

// ------------------------- 链表基本操作函数 -------------------------

/**
 * @brief 创建一个新的数据结点（非头结点）
 * @param value 要插入的字符
 * @return 成功返回指向新结点的指针，失败返回 NULL
 */
link createNode(char value) {
    link node = (link)malloc(sizeof(node));  // 动态申请内存
    if (!node) return NULL;                   // 申请失败返回 NULL
    node->data = value;                       // 赋值数据域
    node->next = NULL;                        // 初始化 next 指针为 NULL
    return node;
}

/**
 * @brief 初始化一个带头结点的空链表
 * @param head 指向链表头指针的指针（允许修改头指针）
 */
void initNode(link *head) {
    link node = (link)malloc(sizeof(node));  // 申请头结点内存
    if (!node) return;
    node->data = '0';                        // 头结点数据域无实际意义，用占位符
    node->next = NULL;                       // 初始化 next
    *head = node;                           // 传出头结点指针
}

/**
 * @brief 头插法插入结点
 * @param head 链表头指针（带头结点）
 * @param value 插入的字符
 */
void insertHead(link head, char value) {
    if (!head) return;
    link node = createNode(value);
    if (!node) return;
    node->next = head->next;  // 新节点指向当前第一个数据节点
    head->next = node;        // 头结点指向新节点
}

/**
 * @brief 尾插法插入结点
 * @param head 链表头指针（带头结点）
 * @param value 插入的字符
 */
void insertTail(link head, char value) {
    if (!head) return;
    link node = createNode(value);
    if (!node) return;

    link cur = head;
    // 遍历找到链表尾部
    while (cur->next) {
        cur = cur->next;
    }
    cur->next = node;  // 尾部追加新节点
}

/**
 * @brief 打印链表中的所有数据结点
 * @param head 链表头指针（带头结点）
 */
void printList(link head) {
    if (head == NULL) return;
    link cur = head->next;  // 跳过头结点
    while (cur != NULL) {
        printf("value is %c\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * @brief 释放整个链表（包括头结点）
 * @param head 指向链表头指针的指针
 */
void destroy(link *head) {
    if (!head || !*head) return;
    link cur = *head;
    while (cur) {
        link temp = cur->next;
        free(cur);
        cur = temp;
    }
    *head = NULL;  // 防止野指针
    printf("SUCCESS\n");
}

// ------------------------- 判断是否为子序列 -------------------------

/**
 * @brief 判断链表 lb 是否为链表 la 的子序列（连续匹配）
 * @param la 主链表（带头结点）
 * @param lb 待检测子链表（带头结点）
 * @return true 表示 lb 是 la 的连续子序列，false 否
 *
 * @note 实现逻辑：
 *  遍历 la 中每个结点作为潜在匹配起点，
 *  尝试与 lb 顺序匹配所有结点，
 *  若 lb 遍历完则说明匹配成功
 */
bool isSubsequence(link la, link lb) {
    if (la == NULL || la->next == NULL) return false;  // 空链表或无数据结点，返回假
    if (lb == NULL || lb->next == NULL) return false;  // 空链表或无数据结点，返回假

    link pa = la->next;  // 主链表数据结点起点
    while (pa != NULL) {
        link pb = lb->next;  // 子链表起点
        link paa = pa;       // 主链表当前起点临时指针

        // 尝试连续匹配
        while (pb != NULL && paa != NULL) {
            if (pb->data == paa->data) {
                pb = pb->next;
                paa = paa->next;
            } else {
                break; // 一旦不匹配，中断匹配尝试
            }
        }

        // 如果 pb 遍历到 NULL，说明匹配成功
        if (pb == NULL) {
            return true;
        }
        pa = pa->next;  // 主链表往后移动一个结点，尝试新起点匹配
    }

    return false;  // 遍历完均未找到匹配连续子序列
}

// ------------------------- 主函数测试 -------------------------

int main() {
    // 初始化链表 head1：a → b → c
    link head1 = NULL;
    initNode(&head1);
    insertTail(head1, 'a');
    insertTail(head1, 'b');
    insertTail(head1, 'c');

    printList(head1);

    // 初始化链表 head2：b → d
    link head2 = NULL;
    initNode(&head2);
    // insertTail(head2, 'b');
    insertTail(head2, 'g');

    printList(head2);

    // 判断 head2 是否为 head1 的连续子序列
    bool flag = isSubsequence(head1, head2);

    if (flag == true) {
        printf("head2 is head1's sequence\n");
    } else {
        printf("head2 is NOT head1's sequence\n");
    }

    // 释放内存
    destroy(&head1);
    destroy(&head2);

    return 0;
}
